/**
 * 数位积是数位和倍数的数的数量
 * 
 * 注意到只可能是2/3/5/7的因子，且因子数量最多是27个
 * 但各个搭配肯定到不了最大值，据说最多只有3000多
 * 使用结构体加哈希作为DP目标
 * status设置为 {2/3/5/7因子数量,数位和,是否有0}
 * D[N][status]，其中D[N]是哈希表
 * 并且在status内部提供isok()的判断
 * 注意前导0需要判断
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using llt = long long;

struct _t{
    // {2、3、5、7的因子数量，数位和，是否有0}
    array<int, 6> a; 
    _t():a{0}{}
    _t(int a0,int a1,int a2,int a3,int a4,int has):a{a0,a1,a2,a3,a4,has}{}
    // 看是否能整除
    bool isok()const{
        static const array<int, 4> A {2,3,5,7};
        if(a[5]) return true;
        auto t = a[4];
        for(int i=0;i<4;++i){
            int k = 0;
            while(0 == t % A[i]){
                t /= A[i]; k += 1;
            }
            if(k > a[i]) return false;
        }
        return t == 1;
    }
};

template<> struct std::tr1::hash<_t>{
    static std::size_t splitmix64(std::size_t x){
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);        
    }

    std::size_t operator () (const _t & t) const {
        static const std::size_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        auto ans = FIXED_RANDOM;
        for(auto i : t.a){
            ans = splitmix64(ans + i);
        }
        return ans;
    }
};

template<> struct std::equal_to<_t>{ // 判相等
    bool operator ()  (const _t & lhs, const _t & rhs) const {
        for(int i=0;i<5;++i){
            if(lhs.a[i] != rhs.a[i]) return false;
        }
        return true;
    }
};

int Limit;
vector<int> G;
// D[i][status], status有5个成员，分别表示到目前为止2357因子数量与数位和
array<__gnu_pbds::gp_hash_table<_t, llt>, 11> D;

llt dfs(int pos, const _t & status, bool lead, bool limit){
    if(-1 == pos) {
        return not lead and status.isok() ? 1 : 0;
    }
    if(not lead and not limit) {
        auto it = D[pos].find(status);
        if(it != D[pos].end()){
            return it->second;
        }        
    }
    int last = limit ? G[pos] : 9;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(status.a[5]){
            ans += dfs(pos - 1, status, lead&&0==i, limit&&0==i);
        }else if(0 == i){
            if(lead){
                ans += dfs(pos - 1, status, true, limit&&last==i);
            }else{
                ans += dfs(pos - 1, {0,0,0,0,0,1}, false, limit&&last==i);
            }
        }else{ // 计算i的因子
            const array<int, 4> A {2,3,5,7};
            array<int, 4> tmp{0,0,0,0};
            int o = i;
            for(int j=0;j<4;++j){
                while(0 == o % A[j]){
                    o /= A[j], tmp[j] += 1;
                }
            }
            ans += dfs(
                pos - 1, 
                _t{status.a[0]+tmp[0],status.a[1]+tmp[1],status.a[2]+tmp[2],status.a[3]+tmp[3],status.a[4]+i,0},
                false,
                limit&&last==i
            );
        }
    }
    if(not lead and not limit){
        D[pos].insert({status, ans});
    }    
    return ans;
}

llt digitDP(int n){
    G.clear();
    while(n){
        G.emplace_back(n % 10);
        n /= 10;
    }
    return dfs(G.size()-1, {0,0,0,0,0,0}, true, true);
}

class Solution {
public:
    int beautifulNumbers(int l, int r) {
        auto t2 = digitDP(r);
        auto t1 = digitDP(l - 1);
        return t2 - t1;            
    }
};

